package com.qying.sort;


/**
 * 堆排序
 */
public class HeapSort {

    public static void main(String[] args) {

        int[] arr = Number.arr;

        for (int i : arr) {
            System.out.print(i + ",");
        }
        System.out.println();

        arr = heapSort(arr);

        for (int i : arr) {
            System.out.print(i + ",");
        }

    }

    static int len;

    private static int[] heapSort(int[] arr) {
        len = arr.length;
        if (len < 1) return arr;
        buidMaxHeap(arr);

        while (len > 0){
            swap(arr,0,len-1);
            len--;
            adjustHeap(arr,0);
        }

        return arr;

    }

    private static void buidMaxHeap(int[] arr) {

        for (int i = (len/2-1); i >= 0; i--){
            adjustHeap(arr,i);
        }
    }

    private static void adjustHeap(int[] arr, int i) {
        int maxIndex = i;

        if (i*2 < len && arr[i * 2] > arr[maxIndex])
            maxIndex = i*2;
        if (i*2 +1 < len && arr[i*2 +1] > arr[maxIndex])
            maxIndex = i*2+1;

        if (maxIndex != i) {
            swap(arr,maxIndex,i);
            adjustHeap(arr,maxIndex);
        }
    }

    private static void swap(int[] arr, int maxIndex, int i) {

        int temp = arr[maxIndex];
        arr[maxIndex] =arr[i];
        arr[i] = temp;
    }


}
